package week02

// 1482. 制作 m 束花所需的最少天数
// https://leetcode-cn.com/problems/minimum-number-of-days-to-make-m-bouquets/

func minDays(bloomDay []int, m int, k int) int {
	var minDay, maxDay = 1000000001, 0
	for _, bloom := range bloomDay {
		minDay = min(minDay, bloom)
		maxDay = max(maxDay, bloom)
	}
	maxDay += 1 // 多一天，表示没有答案
	var limit = maxDay
	for minDay < maxDay {
		var day = (maxDay - minDay) / 2 + minDay
		if isValid(bloomDay, m, k, day) {
			maxDay = day
		} else {
			minDay = day + 1
		}
	}
	if maxDay == limit {
		return -1
	}
	return maxDay
}

func isValid(bloomDay []int, m int, k int, day int) bool {
	var hua = 0
	var group = 0
	for _, bloom := range bloomDay {
		if bloom <= day { // 开花了
			hua++
			if hua == k {
				group++
				hua = 0
			}
		} else {
			hua = 0
		}
	}
	return group >= m
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}